Move notebook to /lib
[andmenj-acm.git] / UVa / 10841 - Lift hopping in the real world / 10841.cpp
blob3c8b110dc1defcaa4a5c321212c89dc029fb79e7
1 #include <sstream>
2 #include <queue>
3 #include <iostream>
4 #include <vector>
6 using namespace std;
8 struct edge{
9 int to, weight, lift;
10 edge(int t, int w, int l) : to(t), weight(w), lift(l) {}
11 bool operator < (const edge &that) const{
12 return weight > that.weight;
16 int main(){
17 int n, k;
18 while (cin >> n >> k){
19 vector<edge> g[100];
20 vector<int> floors[n]; //List of floors visited by elevator i-th
21 int t[n];
22 for (int i=0; i<n; ++i){
23 cin >> t[i];
25 string line;
26 getline(cin, line);
27 for (int i=0; i<n; ++i){
28 getline(cin, line);
29 stringstream ss(line);
30 int x, y;
31 ss >> x;
32 floors[i].push_back(x);
33 while (ss >> y){
34 floors[i].push_back(y);
35 g[x].push_back(edge(y, (y-x)*t[i], i));
36 g[y].push_back(edge(x, (y-x)*t[i], i));
37 x = y;
41 int d[100][n];
42 for (int i=0; i<100; ++i) for (int j=0; j<n; ++j) d[i][j] = INT_MAX;
44 priority_queue<edge> q;
46 for (int j=0; j<n; ++j){
47 if (floors[j].front() == 0){
48 //cout << "Starting at elevator " << j << " ends at floor " << floors[j].back() << endl;
49 d[0][j] = floors[j].back() * t[j];
50 q.push(edge(0, d[0][j], j));
54 if (k == 0){
55 cout << "0" << endl;
56 continue;
59 while (q.size()){
60 edge top = q.top(); q.pop();
62 if (top.to == k) break;
63 if (d[top.to][top.lift] < top.weight) continue;
65 for (int i=0; i<g[top.to].size(); ++i){
66 edge u = g[top.to][i];
68 int tmp;
69 if ((tmp = top.weight + u.weight + (top.lift != u.lift?(max(top.to - floors[u.lift].front(), floors[u.lift].back() - top.to)*t[u.lift]+5):0)) < d[u.to][u.lift]){
70 d[u.to][u.lift] = tmp;
71 q.push(edge(u.to, tmp, u.lift));
75 int a = *min_element(d[k], d[k]+n);
76 if (a < INT_MAX)
77 cout << a << endl;
78 else
79 cout << "IMPOSSIBLE" << endl;
83 return 0;